package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *      换句话说，第一个字符串的排列之一是第二个字符串的子串
 *
 * 2. 算法分析
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q008_字符串的排列 {
    // 暴力  时间复杂度为O(n^2)  空间复杂度为O(26*(n2 - n1))  不推荐
    public boolean checkInclusion1(String s1, String s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        if(s1 == null || s2 == null || len2 < len1) {
            return false;
        }
        char[] charArrayS1 = s1.toCharArray();
        char[] charArrayS2 = s2.toCharArray();
        int[] s1freq = new int[26];
        for(Character ch : charArrayS1) {
            s1freq[ch-'a']++;
        }
        // 暴力 扫描s2中所有长度为len1的子串
        for(int i = 0; i + len1 <= len2; i++) {
            if(s1freq[charArrayS2[i] - 'a'] != 0) {
                // 当前字符出现在s2中，如果没有出现，我们就不需要继续判断了，因为所找寻的时连续的
                int[] s2freq = new int[26];
                for(int j = i; j < i + len1; j++) {
                    s2freq[charArrayS2[j] - 'a']++;
                }
                boolean is = true;
                for(int j = 0; j < 26; j++) {
                    if(s1freq[j] != s2freq[j]) {
                        is = !is;
                        break;
                    }
                }
                if(is == true) {
                    return true;
                }
            }
        }
        return false;
    }


    // 滑动窗口  类似于最小覆盖字串的代码
    public boolean checkInclusion2(String s1, String s2) {
        int plen = s1.length(); // 模式串的长度
        int tlen = s2.length(); // 匹配主串
        if(s1 == null || s2 == null || plen > tlen) {
            return false;
        }
        char[] charArrayP = s1.toCharArray();
        char[] charArrayT = s2.toCharArray();
        int[] pFreq = new int[26];
        int[] tFreq = new int[26];
        for(Character ch : charArrayP) {
            pFreq[ch - 'a']++;
        }
        int distances = 0;
        int left = 0;
        int right = 0;
        while(right < tlen) {
            char rightChar = charArrayT[right];
            if(pFreq[rightChar-'a'] == 0) {
                right++;
                continue;
            }
            if(tFreq[rightChar-'a'] < pFreq[rightChar-'a']) {
                distances++;
            }
            tFreq[rightChar-'a']++;
            right++;
            while(distances == plen) {
                if(distances == right - left) {
                    return true;
                }
                char leftChar = charArrayT[left];
                if(pFreq[leftChar-'a'] == 0) {
                    left++;
                    continue;
                }
                if(pFreq[leftChar-'a'] == tFreq[leftChar-'a']) {
                    distances--;
                }
                tFreq[leftChar-'a']--;
                left++;
            }
        }
        return false;
    }
}
